package codingforgreat.class23;

import javax.swing.text.html.parser.Entity;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Class04_FindKMajority {
    //1. 寻找出现频率大于n/2的数
    public static void printHalfMajor(int[] arr) {
        int cadit = 0;//候选
        int HP = 0;//血量
        for (int i = 0; i < arr.length; i++) {
            if(HP == 0){
                cadit = arr[i];
                HP = 1;
            }else if(arr[i] == cadit){
                HP++;
            }else {
                HP--;
            }
        }
        if(HP == 0) {
            System.out.println("no such number.");
            return;
        }
        HP = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == cadit) {
                HP++;
            }
        }
        if (HP > arr.length / 2) {
            System.out.println(cadit);
        } else {
            System.out.println("no such number.");
        }
    }


    public static void printKMajor(int[] arr, int K) {
        if (K < 2) {
            System.out.println("the value of K is invalid.");
            return;
        }
        // 攒候选，cands，候选表，最多K-1条记录！ > N / K次的数字，最多有K-1个
        HashMap<Integer,Integer> cands = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (cands.containsKey(arr[i])) {
                cands.put(arr[i], cands.get(arr[i]) + 1);
            } else { // arr[i] 不是候选
                if (cands.size() == K - 1) { // 当前数肯定不要！，每一个候选付出1点血量，血量变成0的候选，要删掉！
                    allCandsMinusOne(cands);
                } else {
                    cands.put(arr[i], 1);
                }
            }
        }
        // 所有可能的候选，都在cands表中！遍历一遍arr，每个候选收集真实次数
        HashMap<Integer, Integer> reals = getReals(arr, cands);
        boolean hasPrint = false;
        for (Map.Entry<Integer, Integer> set : cands.entrySet()) {
            Integer key = set.getKey();
            if (reals.get(key) > arr.length / K) {
                hasPrint = true;
                System.out.print(key + " ");
            }
        }
        System.out.println(hasPrint ? "" : "no such number.");
    }

    public static void allCandsMinusOne(HashMap<Integer,Integer> cands) {
        ArrayList<Integer> removeList = new ArrayList<>();
        for(Map.Entry<Integer,Integer> set : cands.entrySet()){
            Integer key = set.getKey();
            Integer value = set.getValue();
            if (value == 1) {
                removeList.add(key);
            }
            cands.put(key, value - 1);
        }
        for (int i = 0; i < removeList.size(); i++) {
            cands.remove(removeList.get(i));
        }
    }

    public static HashMap<Integer, Integer> getReals(int[] arr,
                                                     HashMap<Integer, Integer> cands) {
        HashMap<Integer, Integer> reals = new HashMap<Integer, Integer>();
        for (int i = 0; i != arr.length; i++) {
            int curNum = arr[i];
            if (cands.containsKey(curNum)) {
                if (reals.containsKey(curNum)) {
                    reals.put(curNum, reals.get(curNum) + 1);
                } else {
                    reals.put(curNum, 1);
                }
            }
        }
        return reals;
    }


    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 1, 1, 2, 1 };
        printHalfMajor(arr);
        int K = 4;
        printKMajor(arr, K);
    }
}
